package codingforgreat.class39;


// 来自京东
// 给定一个二维数组matrix，matrix[i][j] = k代表:
// 从(i,j)位置可以随意往右跳<=k步，或者从(i,j)位置可以随意往下跳<=k步
// 如果matrix[i][j] = 0，代表来到(i,j)位置必须停止
// 返回从matrix左上角到右下角，至少要跳几次
// 已知matrix中行数n <= 5000, 列数m <= 5000
// matrix中的值，<= 5000
// 最弟弟的技巧也过了。最优解 -> dp+枚举优化(线段树，体系学习班)
public class Class04_JumpGameOnMatrix {
    // 暴力方法，仅仅是做对数器
    // 如果无法到达会返回系统最大值
    public static int jump1(int[][] map) {
        return process(map, 0, 0);
    }
    public static int process(int[][] map, int row, int col) {
        if (row == map.length - 1 && col == map[0].length - 1) {
            return 0;
        }
        if(map[row][col] == 0){
            return Integer.MAX_VALUE;
        }
        int next = Integer.MAX_VALUE;
        for (int down = row + 1; down < map.length && (down - row) <= map[row][col]; down++) {
            next = Math.min(next, process(map, down, col));
        }
        // 往右能到达的位置，全试一遍
        for (int right = col + 1; right < map[0].length && (right - col) <= map[row][col]; right++) {
            next = Math.min(next, process(map, row, right));
        }
        // 如果所有下一步的位置，没有一个能到右下角，next = 系统最大！
        // 返回系统最大！
        // next != 系统最大 7 + 1
        return next != Integer.MAX_VALUE ? (next + 1) : next;
    }

    public static int jump2(int[][] arr){
      int N = arr.length;
      int M = arr[0].length;
      int[][] map = new int[N + 1][M + 1];
        for (int a = 0, b = 1; a < N; a++, b++) {
            for (int c = 0, d = 1; c < M; c++, d++) {
                map[b][d] = arr[a][c];
            }
        }
        SegmentTree[] rowTrees = new SegmentTree[N + 1];
        for(int i = 1;i <= N;i++){
            rowTrees[i] = new SegmentTree(M);
        }
        SegmentTree[] colTrees = new SegmentTree[M + 1];
        for (int i = 1; i <= M; i++) {
            colTrees[i] = new SegmentTree(N);
        }
        rowTrees[N].update(1,M,M,0,1,M);
        colTrees[M].update(1,N,N,0,1,N);
        for (int col = M - 1; col >= 1; col--) {
            if (map[N][col] != 0) {
                int left = col + 1;
                int right = Math.min(col + map[N][col], M);
                int next = rowTrees[N].query(1,left,right,1,M);
                if (next != Integer.MAX_VALUE) {
                    rowTrees[N].update(1,col,col,next + 1,1,M);
                    colTrees[col].update(1,N,N,next + 1,1,N);
                }
            }
        }
        for (int row = N - 1; row >= 1; row--) {
            if (map[row][M] != 0) {
                int up = row + 1;
                int down = Math.min(row + map[row][M], N);
                int next = colTrees[M].query(1,up,down,1,N);
                if (next != Integer.MAX_VALUE) {
                    rowTrees[row].update(1,M,M,next + 1,1,M);
                    colTrees[M].update(1,row,row,next + 1,1,N);
                }
            }
        }
        for (int row = N - 1; row >= 1; row--) {
            for (int col = M - 1; col >= 1; col--) {
                if (map[row][col] != 0) {
                    // (row,col) 往右是什么范围呢？[left,right]
                    int left = col + 1;
                    int right = Math.min(col + map[row][col], M);
                    int next1 = rowTrees[row].query(1,left, right, 1, M);
                    // (row,col) 往下是什么范围呢？[up,down]
                    int up = row + 1;
                    int down = Math.min(row + map[row][col], N);
                    int next2 = colTrees[col].query(1,up, down, 1, N);
                    int next = Math.min(next1, next2);
                    if (next != Integer.MAX_VALUE) {
                        rowTrees[row].update(1,col, col, next + 1, 1, M);
                        colTrees[col].update(1,row, row, next + 1, 1, N);
                    }
                }
            }
        }
        return rowTrees[1].query(1,1, 1, 1, M);
    }

    public static class SegmentTree{
        public int[] min;
        public int[] change;
        public boolean[] update;

        public SegmentTree(int size) {
        int N = size + 1;
        min = new int[N << 2];
        change = new int[N << 2];
        update = new boolean[N << 2];
        update(1,1,size,Integer.MAX_VALUE,1,size);
        }
        public void pushUp(int rt){
            min[rt] = Math.min(min[rt << 1],min[rt << 1 | 1]);
        }
        public void pushDown(int rt,int ln,int rn){
            if(update[rt]){
                update[rt << 1] = true;
                update[rt << 1 | 1] = true;
                change[rt <<1] =  change[rt];
                change[rt << 1 | 1] = change[rt];
                min[rt << 1] =  change[rt];
                min[rt << 1 | 1] = change[rt];
                update[rt] = false;
            }
        }
        public void update(int rt,int L,int R,int C,int l,int r){
            if(L <= l && R >= r){
                update[rt] = true;
                change[rt] = C;
                min[rt] = C;
                return;
            }
            int M = (l + r) >> 1;
            pushDown(rt,M - l + 1,r - M );
            if(L <= M){
                update(rt << 1,L,R,C,l,M);
            }
            if(R > M){
                update(rt << 1 | 1,L,R,C,M + 1,r);
            }
            pushUp(rt);
        }
        public int query(int rt,int L,int R,int l,int r){
            if(L <= l && R >= r){
                return min[rt];
            }
            int M = (l + r) /2;
            pushDown(rt,M - l + 1,r - M );
            int left = Integer.MAX_VALUE;
            int right = Integer.MAX_VALUE;
            if(L <= M){
             left =  query(rt << 1,L,R,l,M);
            }
            if(R > M){
             right =  query(rt << 1 | 1,L,R,M + 1,r);
            }
            return Math.min(left,right);
        }
    }
    // 为了测试
    public static int[][] randomMatrix(int n, int m, int v) {
        int[][] ans = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                ans[i][j] = (int) (Math.random() * v);
            }
        }
        return ans;
    }

    // 为了测试
    public static void main(String[] args) {
        // 先展示一下线段树的用法，假设N=100
        // 初始化时，1~100所有位置的值都是系统最大
        System.out.println("线段树展示开始");
        int N = 100;
        SegmentTree st = new SegmentTree(N);
        // 查询8~19范围上的最小值
        System.out.println(st.query(8, 19, 1, N, 1));
        // 把6~14范围上对应的值都修改成56
        st.update(6, 14, 56, 1, N, 1);
        // 查询8~19范围上的最小值
        System.out.println(st.query(8, 19, 1, N, 1));
        // 以上是线段树的用法，你可以随意使用update和query方法
        // 线段树的详解请看体系学习班
        System.out.println("线段树展示结束");

        // 以下为正式测试
        int len = 10;
        int value = 8;
        int testTimes = 10000;
        System.out.println("对数器测试开始");
        for (int i = 0; i < testTimes; i++) {
            int n = (int) (Math.random() * len) + 1;
            int m = (int) (Math.random() * len) + 1;
            int[][] map = randomMatrix(n, m, value);
            int ans1 = jump1(map);
            int ans2 = jump2(map);
            if (ans1 != ans2) {
                System.out.println("出错了!");
            }
        }
        System.out.println("对数器测试结束");
    }

}
